package com.mokairui.sort.advanced;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

import static com.mokairui.sort.base.Selection.exch;

/**
 * @Description 快速排序
 * @Author Mokairui
 * @Since 2021/10/10
 */
@Slf4j(topic = "c.quick")
public class Quick {
    public static void main(String[] args) {
        Integer[] arr = {4, 5, 6, 3, 2, 1};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int start, int end) {
        // 安全性校验
        if (start >= end) {
            return;
        }

        // 需要对数组中 start 索引到 end 索引处的元素进行分组(左子树和右子树)
        int partition = partition(arr, start, end);
        // 让左子树有序
        sort(arr, start, partition - 1);
        // 让右子树有序
        sort(arr, partition + 1, end);
    }

    // 对数组arr中, 从索引 start 到索引 end 之间的元素进行分组, 并返回分组界限对应的索引
    private static int partition(Comparable[] arr, int start, int end) {
        // 确定分界值
        Comparable key = arr[start];
        // 定义两个指针, 分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = start;
        int right = end + 1;

        while (true) {
            // 先从左往右扫描, 移动right指针, 找到一个比分界值小的元素, 停止
            while (less(key, arr[--right])) {
                if (right == start) {
                    break;
                }
            }
            // 再从左往右扫描, 移动left指针, 找到一个比分界值大的元素, 停止
            while (less(arr[++left], key)) {
                if (left == end) {
                    break;
                }
            }
            // 判断 left >= right, 如果是, 则证明元素扫描完毕, 结束循环, 如果不是, 则交换元素即可
            if (left >= right) {
                break;
            } else {
                exch(arr, left, right);
            }
        }
        exch(arr, start, end);
        return right;
    }

    private static boolean less(Comparable key, Comparable comparable) {
        return key.compareTo(comparable) < 0;
    }


}
